package com.sicheng.algorithm.recursive;

/**
 * @author : zsc
 */
public class FindDuplication {
    public static void main(String[] args) {
        int[] nums = {1, 4, 2, 1, 3, 3};
        System.out.println(findDuplication(nums));
    }

    public static int findDuplication(int[] nums) {
        if (nums == null || nums.length < 2)
            return -1;
        return findDuplication(nums, 1, nums.length - 1);
    }

    public static int findDuplication(int[] nums, int start, int end) {
        int count = 0;
        int mid = (start + end) / 2;
        for (int num : nums) {
            if (num >= start && num <= mid)
                count++;
        }
        if (count > (mid - start + 1) && start != end)
            return findDuplication(nums, start, mid);
        if (count <= (mid - start + 1) && start != end)
            return findDuplication(nums, mid + 1, end);
        else
            return start;
    }
}
